package com.datastructure3.linkedlist;

import javax.swing.plaf.ComponentUI;

/**
 * @author: 临晖
 * @since: 2024-07-15
 */
public class Solution {

    /**
     * 203. 移除链表元素
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode node = new ListNode();

        node.next = head;
        head = node;

        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
                continue;
            }

            node = node.next;
        }

        return head.next;
    }


    /**
     * 206. 反转链表
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        //return reverse(head, null);

        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;

            curr.next = pre;
            pre = curr;
            curr = next;
        }

        return pre;

    }

    public ListNode reverse(ListNode node, ListNode pre) {
        if (node == null) {
            return pre;
        }


        ListNode temp = node.next;

        node.next = pre;

        return reverse(temp, node);

    }


    /**
     *
     * 24. 两两交换链表中的节点
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return head;
        }


        ListNode first = new ListNode();
        first.next = head;

        ListNode curr = first;

        while (curr.next != null && curr.next.next != null) {
            ListNode temp = curr.next;
            curr.next = curr.next.next;
            temp.next = temp.next.next;
            curr.next.next = temp;

            curr = temp;
        }

        return first.next;
    }


    /**
     *
     * 19. 删除链表的倒数第 N 个结点
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = new ListNode();
        first.next = head;
        ListNode next = first;
        ListNode pre = first;

        int count = 1;
        while (next.next != null) {
            if (count > n) {
                pre = pre.next;
            }

            next = next.next;
            count++;
        }

        pre.next = pre.next.next;

        return first.next;
    }


    /**
     *
     * 面试题 02.07. 链表相交
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
     * 图示两个链表在节点 c1 开始相交：
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int countA = 0;
        int countB = 0;

        ListNode currA = headA;
        ListNode currB = headB;

        while (currA != null) {
            currA = currA.next;
            countA++;
        }

        while (currB != null){
            currB = currB.next;
            countB++;
        }

        currA = headA;
        currB = headB;
        int len = Math.abs(countA - countB);



        if (countA > countB) {
            while (len-- > 0) {
                currA = currA.next;
            }
        } else {

            while (len-- > 0) {
                currB = currB.next;
            }
        }

        while (currA != null) {
            if (currA == currB) {
                return currA;
            }

            currA = currA.next;
            currB = currB.next;
        }

        return null;
    }


    /**
     *
     * 142. 环形链表 II
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * 不允许修改 链表。
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

       while (fast != null) {
           slow = slow.next;

           if (fast.next == null) {
               return null;
           }
           fast = fast.next.next;

           if (slow == fast) {
              break;
           }
       }

       if (fast == null) {
           return null;
       }

       fast = head;
       while (fast != slow) {
           fast = fast.next;
           slow = slow.next;
       }

       return slow;

    }


}




